This invention relates to a connected word recognition method of automatically recognizing, as an optimum one of word concatenations, an input string of words represented by an input sequence of input pattern feature vectors.
The input string of words is selected from a word set of first through N-th words and substantially continuously uttered in compliance with a regular grammar, or a grammar of regular languages, known in the art. Each concatenation is a string of words selected from the word set and conatenated in compliance with the grammar. The grammar specifies a set of transition rules for the first through the N-th words and a set of final states of the concatenations. The transition rule for an n-th word optionally selected from the word set, defines a combination of the n-th word and a state pair consisting of a start and an end state of the n-th word.
A connected word recognition system for use in carrying out the connected word recognition method, is disclosed in U.S. Pat. No. 4,555,796 issued to Hiroaki Sakoe. The connected word recognition system uses a DP (dynamic programming) matching algorithm based on frame synchronization known in the art. That is, the connected word recognition system operable according to a DP algorithm and in compliance with the regular grammar, is put into operation in synchronism with successive specification of the input pattern feature vectors of the input string in the following manner.
In the Sakoe patent, the connected word recognition system comprises a reference pattern memory for memorizing reference pattern feature vectors representative of the first through the N-th words. The reference pattern feature vectors representative of the n-th word are consecutively numbered as first through J-th feature vectors according to utterance of the n-th word.
A control circuit is for generating a basic timing signal successively specifying first through I-th periods assigned to the respective input pattern feature vectors, a word specifying signal specifying, while an i-th period is specified as each of the first through the I-th periods, the first through the N-th words, and a state specifying signal specifying, while the i-th period is specified, the state pairs of the first through the N-th words.
A distance calculating circuit is responsive to the input sequence and is connected to the reference pattern memory and the control circuit for calculating, while the n-th word is specified in the i-th period, a plurality of distances between the input pattern feature vector assigned to the i-th period and the first through the J-th feature vectors.
A minimum finding circuit is connected to the control circuit and the distance calculating circuit for calculating, while the n-th word and each state pair of the n-th word are specified in the i-th period, a recurrence value g(n, i, j) for the n-th word and the each state pair under a boundary condition iteratively in correspondence to the first through the J-th feature vectors by using the distances calculated for the n-th word before the i-th period, where n represents the n-th word, i represents the i-th period, and j represents a j-th feature vector representative of each of the first through the J-th feature vectors.
The minimum finding circuit is for finding, while the i-th period is specified, a minimum T(q, i) of the recurrence values calculated for the words having state pairs including the end state q of the each state pair.
The minimum finding circuit is for deciding that particular word and that particular start state of the particular word for which the minimum is found. The boundary condition is given by T(p, i-1), where p represents the start state of the each state pair.
A start period selecting circuit is connected to the control circuit and the minimum finding circuit for selecting, while the i-th period is specified, a particular period from the first through the (i-1)-th periods with reference to the particular start state and the particular word.
A deciding circuit is connected to the control circuit, the minimum finding circuit, and the start period selecting circuit for deciding the optimum concatenation by referring, after lapse of the I-th period, to the minima found in the first through the I-th periods, respectively, and to those particular words, those particular start states, and those particular start periods which are decided in the first through the I-th periods.
Inasmuch as the connected word recognition system operates in synchronism with successive specification of the input pattern feature vectors of the input string, the connected word recognition system can carry out real-time processing of the input string. It will be assumed that the n-th word appears in a plural number K of the transition rules as the n-th word of first through K-th occurrence. In this case, the transition rules for the n-th word of the first through the K-th occurrence define different start states which are different from each other. It is therefore necessary to independently carry out processing for the n-th word of the first through the K-th occurrence. This results in an increased amount of calculation.